Software often must be designed and developed as part of a large and complex reactive system. A reactive system is utilized in a variety of applications, such as, telecommunications, automobiles, computer networks, personal computers, avionic systems, process controls, man-machine interfaces, and other systems. Generally, reactive systems are event driven and continuously react to external and internal stimuli. The external and internal stimuli can be human operator initiated or can be provided from completely external equipment or happenings.
One type of reactive system is a graphical user interface for flight plan editing in a graphical flight management system (FMS). Developing software for a reactive system, such as, the graphical user interface, requires that the behavior of the reactive system be modeled or represented in a formal fashion.
Generally, the reactive system can be modeled or represented as a state machine. A state machine is an abstract control model consisting of a set of states, a set of input events, a set of output actions and a state transition function. A function takes the current state and an input event and returns a set of output events and the next state. Some states may be designated as “terminal states.” A terminal state is an ending state from which the state machine does not exit.
The state machine can also be viewed as a function which maps an ordered sequence of input events into a corresponding sequence of (sets of) output events. State machines are often represented by state transition diagrams to effectively specify the behavior of reactive systems. Statecharts are a type of state transition diagram described in more detail below. Statecharts efficiently represent a set of states and the transition between states based upon events. The graphical notation associated with statecharts is easily understandable and can be utilized to support discussions and conversations about the system. Such a representation or graphical notation is highly valuable when evaluating the workings of a graphical user interface.
State machines can be deterministic or non-deterministic. A deterministic state machine is one where the next state is uniquely determined by a single input event. A non-deterministic state machine may have several possible next states for a given input event. The next state that is actually chosen may either be chosen randomly or it may be chosen based upon an arbitrary number of subsequent input events. In the latter case, until these subsequent events occur, it is not possible to determine the state within which the machine resides. It is generally possible to automatically translate a non-deterministic state machine into a deterministic one which will produce the same output given the same input.
Simple statecharts or state transition diagrams, such as deterministic finite automations (DFA), have been utilized to study languages, such as programming languages. The goal of such simple state transition diagrams is to allow the state machine to determine whether or not a given word is contained in a language. A DFA has a finite set of states and transitions where each transition leads from one state to another. Each transition is associated with a particular input character; the transition can only cause a change in the active state when that particular input character is read from the input word. At any given time, only one of the states is active, i.e., the next input character (read from the word to be recognized) is able to activate only those transitions that depart from the active state.
One state is the designated start position (it is active state when the first input character is read). One or more states are defined as terminating states. After the input word has been read completely, if the state machine has arrived to a terminating state, the word is accepted. Otherwise, the word is rejected (i.e., not in the language recognized by the DFA). The set of a languages that can be recognized by DFAs equals the set of languages that can be described using regular expressions. Therefore, this set of languages is called regular languages.
Several extensions of more advanced concepts of state transition systems have been proposed. Some extensions introduce more complex languages than regular languages and others better support tasks not related to programming languages. As a trend of controlling systems by computers and software increases, many more systems are represented as being state based. Using automations and state transition diagrams to specify these systems becomes increasingly more popular and effective. A significant difference between the described conventional extensions and more advanced concepts to state transition systems when compared to DFAs is that these extensions do not include a terminating state. Although these computer systems can be switched off and thus are forced to terminate, these systems no longer recognize or reject words of finite length.
DFAs are not appropriate for more complex application which do not include terminating states. With the exception of certain military applications, the complex systems are often designed so that they can potentially operate forever. Although it is possible to specify behavior of a complex system such as a graphical interface (GUI) using DFAs, an exceedingly large number of transitions and states is necessary due to global options and parallel execution, respectively.
Another difference between the described conventional extensions and more advanced concepts is that state transitions in complex systems are not triggered by characters read from an input word as in a DFA system. Rather, external events drive the systems. For example, external events can be keystrokes, expiration of timers, arrival of messages from another computer, sensor signals, mouse clicks, etc. These events are called external because their source is outside of the state machine. The events are also discrete in that they either occur or do not occur. Events which are recognized by the state machine can lead to changes or transitions in the state. Events that are not recognized do not cause a change in the active state (the system continues to run in its present active state). There is no equivalence of rejecting an input word as utilized in a DFA.
Generally, non-deterministic statecharts can be converted to an equivalent deterministic statechart if both machines recognize the same language. However, the deterministic statechart becomes extremely complex because the definition of equivalence of automations is not helpful. Also, there is a need for a deterministic statechart that can provide a specification for a reactive system. One type of statechart system utilizes a Harel statechart which is fully described in Harel, “Statecharts: A Visual Formalism for Complex Systems” Science of Computer Programming 8 (1987), pp. 231-274. Harel statecharts are well known by one of ordinary skill in the art. However, Harel statecharts are not deterministic. There is nothing in its rules which prevent two different states from being the result of the same input criteria.
Thus, there is a need for a deterministic state machine defined by statecharts. Further, there is a need for a deterministic statechart that can be used to design complex reactive systems, such as, avionic software. Further still, there is a need for a modified Harel statechart which is deterministic.